#include "ff_graph.h"
#include <algorithm>

void ff_graph::to_delay(char* delay_file)
{
    FILE *fp_delay = fopen (delay_file, "w");

    if (fp_delay == NULL) 
    {
        perror ("Error opening delay file");
    }
    else
    {
        rewind (fp_delay); 
    }

    const float corr[] = {
        +4.150304e-001, +3.271902e-001, -4.057111e-001, +4.208730e-001, 
        +3.037974e-001, -9.304737e-016, +1.364467e-001, +3.828222e-001, 
        +1.024550e-001, -4.775609e-002, -2.204876e-001, -1.802484e-001, 
        -2.562933e-015, -2.500675e-002, -1.531527e-001, -5.945059e-002, 
        +5.240960e-001, +4.897078e-001, -2.421553e-001, +2.289197e-001, 
        +1.039560e-001, +3.378482e-001, -2.486901e-001, +5.649150e-002, 
        +7.083435e-002, +2.079639e-001, +1.519947e-001, +1.119442e-001, 
        -2.178870e-001, +1.150349e-001, +1.719156e-001, +1.015715e-001, 
        +5.240960e-001, +5.298921e-001, +1.329183e-001, -2.289197e-001, 
        +1.039560e-001, +3.378482e-001, -1.135392e-001, -2.283570e-001, 
        +1.879744e-001, -1.137195e-001, +1.519947e-001, -1.119442e-001, 
        +2.178870e-001, -1.995772e-001, -5.437768e-002, -1.015715e-001, 
        +4.150304e-001, +4.057111e-001, +3.271902e-001, -4.208730e-001, 
        +3.037974e-001, -8.389547e-016, +3.828222e-001, -1.364467e-001, 
        +4.775609e-002, +1.024550e-001, -2.204876e-001, +1.802484e-001, 
        +6.720487e-016, +1.531527e-001, -2.500675e-002, +5.945059e-002, 
        +5.240960e-001, +1.329183e-001, -5.298921e-001, +2.289197e-001, 
        +1.039560e-001, -3.378482e-001, +2.283570e-001, -1.135392e-001, 
        -1.137195e-001, -1.879744e-001, +1.519947e-001, +1.119442e-001, 
        +2.178870e-001, -5.437768e-002, +1.995772e-001, +1.015715e-001, 
        +6.711793e-001, +2.356243e-001, -2.921708e-001, +1.257038e-001, 
        -3.502060e-001, +7.925524e-016, -5.878860e-002, -1.649405e-001, 
        -3.273625e-001, +1.525895e-001, -1.010320e-001, +1.957712e-001, 
        +8.963410e-016, -2.852761e-002, -1.747161e-001, -1.708963e-001, 
        +6.711793e-001, +2.921708e-001, +2.356243e-001, -1.257038e-001, 
        -3.502060e-001, +1.078709e-015, -1.649405e-001, +5.878860e-002, 
        -1.525895e-001, -3.273625e-001, -1.010320e-001, -1.957712e-001, 
        -1.530303e-015, +1.747161e-001, -2.852761e-002, +1.708963e-001, 
        +5.240960e-001, +2.421553e-001, +4.897078e-001, -2.289197e-001, 
        +1.039560e-001, -3.378482e-001, +5.649150e-002, +2.486901e-001, 
        -2.079639e-001, +7.083435e-002, +1.519947e-001, -1.119442e-001, 
        -2.178870e-001, -1.719156e-001, +1.150349e-001, -1.015715e-001, 
        +5.240960e-001, -2.421553e-001, -4.897078e-001, -2.289197e-001, 
        +1.039560e-001, -3.378482e-001, -5.649150e-002, -2.486901e-001, 
        +2.079639e-001, -7.083435e-002, +1.519947e-001, -1.119442e-001, 
        -2.178870e-001, +1.719156e-001, -1.150349e-001, -1.015715e-001, 
        +6.711793e-001, -2.921708e-001, -2.356243e-001, -1.257038e-001, 
        -3.502060e-001, +9.011952e-016, +1.649405e-001, -5.878860e-002, 
        +1.525895e-001, +3.273625e-001, -1.010320e-001, -1.957712e-001, 
        -2.216296e-015, -1.747161e-001, +2.852761e-002, +1.708963e-001, 
        +6.711793e-001, -2.356243e-001, +2.921708e-001, +1.257038e-001, 
        -3.502060e-001, +1.057441e-015, +5.878860e-002, +1.649405e-001, 
        +3.273625e-001, -1.525895e-001, -1.010320e-001, +1.957712e-001, 
        +1.544306e-015, +2.852761e-002, +1.747161e-001, -1.708963e-001, 
        +5.240960e-001, -1.329183e-001, +5.298921e-001, +2.289197e-001, 
        +1.039560e-001, -3.378482e-001, -2.283570e-001, +1.135392e-001, 
        +1.137195e-001, +1.879744e-001, +1.519947e-001, +1.119442e-001, 
        +2.178870e-001, +5.437768e-002, -1.995772e-001, +1.015715e-001, 
        +4.150304e-001, -4.057111e-001, -3.271902e-001, -4.208730e-001, 
        +3.037974e-001, -1.069753e-015, -3.828222e-001, +1.364467e-001, 
        -4.775609e-002, -1.024550e-001, -2.204876e-001, +1.802484e-001, 
        +9.480762e-016, -1.531527e-001, +2.500675e-002, +5.945059e-002, 
        +5.240960e-001, -5.298921e-001, -1.329183e-001, -2.289197e-001, 
        +1.039560e-001, +3.378482e-001, +1.135392e-001, +2.283570e-001, 
        -1.879744e-001, +1.137195e-001, +1.519947e-001, -1.119442e-001, 
        +2.178870e-001, +1.995772e-001, +5.437768e-002, -1.015715e-001, 
        +5.240960e-001, -4.897078e-001, +2.421553e-001, +2.289197e-001, 
        +1.039560e-001, +3.378482e-001, +2.486901e-001, -5.649150e-002, 
        -7.083435e-002, -2.079639e-001, +1.519947e-001, +1.119442e-001, 
        -2.178870e-001, -1.150349e-001, -1.719156e-001, +1.015715e-001, 
        +4.150304e-001, -3.271902e-001, +4.057111e-001, +4.208730e-001, 
        +3.037974e-001, -8.045137e-016, -1.364467e-001, -3.828222e-001, 
        -1.024550e-001, +4.775609e-002, -2.204876e-001, -1.802484e-001, 
        -2.406414e-015, +2.500675e-002, +1.531527e-001, -5.945059e-002, };

        assert(sizeof(corr)/sizeof(corr[0]) == 256);

        int num_gauss = VARNUM; //delay colomun

        vertex_delay.clear();
        vector<float> row_delay;
        row_delay.assign(num_gauss, 0.0);
        vertex_delay.assign(vertex_num, row_delay);

        for (unsigned int i = 1; i < vertex_num - 1; ++i)
        {
            float mean_delay = vertex_fanout[i].size();
            if (mean_delay < 1)
                mean_delay = 1;
            if (mean_delay > 100)
                mean_delay = 100;

            vertex_delay[i][0] = mean_delay;
            float max_var = 0.3;
            float min_var = max_var*2.0/3.0;
            float var = (float(rand()) / RAND_MAX * (max_var-min_var) + min_var)
                * mean_delay;

            if (mean_delay <= 0)
            {
                 mean_delay = 1.0;   
            }

            //int x = xy_placement[i*2];
            //int y = xy_placement[i*2+1];
            //int xy = x*4+y;
            int xy = rand() % 15 + 1;
            assert((xy >= 0) && (xy < 16));

            for (unsigned int j = 1; j < num_gauss + 1; ++j)
            {
                vertex_delay[i][j] = var * corr[xy * 16 + j];
            }
        }

        fprintf(fp_delay," %d %d \n", vertex_num, num_gauss);
        for (unsigned int j = 0; j < vertex_num; j++)
        {
            //fprintf(fp_delay, " %d", tp_order[j]); //store vertex by tp_order
            for (unsigned int i = 0; i < num_gauss; ++i) 
            {
                fprintf(fp_delay, " %f", vertex_delay[j][i]);
            }
            fprintf(fp_delay, " \n");
        }

        fclose(fp_delay);
}

bool ff_graph::check_edge_tp(struct edge &e)
{
    for (unsigned int j = 0; j < tp_order.size(); j++)
    {
        if (tp_order[j] == e.in)
        {
            return true;
        }

        if (tp_order[j] == e.out)
        {
            return false;
        }
    }
    return true;
}

void ff_graph::build_dag()
{
    //remove redundant edge
    for (unsigned int v = 0; v < get_vertex_num(); v++)
    {
        vector <int> edge_delete_tag;
        edge_delete_tag.assign(vertex_fanin[v].size(), 0);

        for (unsigned int i = 0; i < vertex_fanin[v].size(); i++)
        {
            struct edge current_edge = vertex_fanin[v][i];

            for (unsigned int j = i + 1; j < vertex_fanin[v].size(); j++)
            {
                if (vertex_fanin[v][j].in == current_edge.in && 
                    vertex_fanin[v][j].out == current_edge.out)
                {
                    edge_delete_tag[j] = 1; //delete
                    break;
                }
            }
        }

        vector <edge> temp_fanin;
        for (unsigned int k = 0; k < vertex_fanin[v].size(); k++)
        {
            if (edge_delete_tag[k] == 0)
            {
                temp_fanin.push_back(vertex_fanin[v][k]);
            }
        }

        vertex_fanin[v].clear();
        vertex_fanin[v].assign(temp_fanin.begin(), temp_fanin.end());
    }

    edge_set.clear();
    for (unsigned int v = 0; v < get_vertex_num(); v++)
    {
        for (unsigned int i = 0; i < vertex_fanin[v].size(); i++)
        {
            edge_set.push_back(vertex_fanin[v][i]);
        }
    }

    vector<edge>::iterator edge_it;
    for (edge_it = edge_set.begin(); edge_it != edge_set.end(); ++edge_it)
    {
        struct edge e = *edge_it;

        while (check_edge_tp(e) == false) 
        {
            edge_it = edge_set.erase(edge_it);

            //check next edge
            if(edge_it == edge_set.end())
            {
                break;
            }
            else
            {
                e = *edge_it;
            }
        }

        if(edge_it == edge_set.end())
        {
            break;
        }
    }
}

void ff_graph::net_to_dag(char* net_file, char* dag_file)
{
    FILE *fp_net = fopen (net_file, "r");
    FILE *fp_dag = fopen (dag_file, "w");

    if (fp_net == NULL || fp_dag == NULL) 
    {
        perror ("Error opening net or dag file");
    }
    else
    {
        rewind (fp_net); 
        rewind (fp_dag); 
    }

    /* 
    * First five lines of net file
    * ignored 
    * #Pins
    * #Nets
    * #Modules
    * pad offset
    */
    int ignored, pins, nets, modules, pad_offset; 
    fscanf(fp_net, " %d \n", &ignored);
    fscanf(fp_net, " %d \n", &pins);
    fscanf(fp_net, " %d \n", &nets);
    fscanf(fp_net, " %d \n", &modules);
    fscanf(fp_net, " %d \n", &pad_offset);

    vertex_num = modules;
    ff_num = modules - pad_offset -1;
    gate_num = pad_offset + 1;

    char buffer [20];
    struct edge e;

    while (fgets(buffer, 20, fp_net) != NULL)
    {
        char * word;
        char * number;
        //printf ("Splitting string \"%s\" into tokens:\n",str);
        word = strtok(buffer," ");

        unsigned int vertex;

        if (strchr(word, 'p') != NULL) //if ff 
        {
            number = &word[1];
            vertex = strtoul (number, NULL, 0);
            vertex = gate_num + (vertex - 1);   //since pad index starts from 1
        }
        else if (strchr(word, 'a') != NULL) // if gate
        {
            number = &word[1];
            vertex = strtoul (number, NULL, 0);
        }

        word = strtok(NULL, " "); 

        //check source vertex or not
        if (strchr(word, 's') != NULL)
        {
            assert(vertex < vertex_num);
            e.in = vertex;
        }
        else 
        {
            assert(vertex < vertex_num);
            e.out = vertex;
            edge_set.push_back(e);
        }
    }

    edge_num = edge_set.size();

    //build dag first
    gen_fanins();
    gen_fanouts();

    tp_sort(); 
    build_dag();

    edge_num = edge_set.size();

    gen_fanins();
    gen_fanouts();

    tp_sort(); 

    fprintf(fp_dag," %d %d %d \n", vertex_num, ff_num, edge_num);

    for (unsigned int i = 0; i < vertex_num; i++)
    {
        vector<edge>::iterator edge_it;
        for (edge_it = vertex_fanin[i].begin(); 
            edge_it != vertex_fanin[i].end(); ++edge_it)
        {    
            struct edge e = (*edge_it);
            fprintf(fp_dag," %d %d\n", e.in, e.out);
        }
    }

    fclose(fp_net);
    fclose(fp_dag);
}

int ff_graph::find_equal_string(string &str, vector<string> &vertex_set)
{
	int index = -1;
	int tmp_idx = 0;
	vector<string>::iterator it;
	for (it = vertex_set.begin(); it < vertex_set.end(); it++)
	{
		string cur_str = *it;
		if (str.compare(cur_str) == 0)
		{
			index = tmp_idx;
			break;
		}
		tmp_idx++;
	}

	return index;
}

void ff_graph::itc_to_dag(char* itc_file, char* dag_file)
{
    FILE *fp_itc = fopen (itc_file, "r");
    FILE *fp_dag = fopen (dag_file, "w");

    if (fp_itc == NULL || fp_dag == NULL) 
    {
        perror ("Error opening itc or dag file");
    }

    vector<string> vertex_set;
	//vector<edge> edge_set;
    vector<string> input_set;
    vector<string> output_set;
    char str_line [100];

    while (fgets(str_line , 100 , fp_itc) != NULL)
    {
        char * pch;
		string str;
        pch = strtok(str_line," ,=()\n");
        while (pch != NULL)
        {
            if (strcmp(pch, "INPUT") == 0) //input equal
            {
                pch = strtok(NULL, " ,=()\n");
				if (pch != NULL)
				{
					str = pch;
					vertex_set.push_back(str);
					input_set.push_back(str);
				}
            }
            else if (strcmp(pch, "OUTPUT") == 0) //output
            {
                pch = strtok(NULL, " ,=()\n");
				if (pch != NULL)
				{
					str = pch;
					vertex_set.push_back(str);
					output_set.push_back(str);
				}
            }
            else //gate 
            {
				unsigned int edge_in;
				unsigned int edge_out;

				str = pch;

				int index = find_equal_string(str, vertex_set);

				//output
				if (index == -1)
				{
					vertex_set.push_back(str);
					edge_out = vertex_set.size() - 1;
				}
				else 
				{
					edge_out = index;
				}

                pch = strtok(NULL, " ,=()\n"); //ignore gate
				pch = strtok(NULL, " ,=()\n");
				while (pch != NULL)
				{
					struct edge e;
					str = pch;

					index = find_equal_string(str, vertex_set);
					if (index == -1)
					{
						vertex_set.push_back(str);
						edge_in = vertex_set.size() - 1;
					}
					else
					{
						edge_in = index;
					}

					e.in = edge_in;
					e.out = edge_out;
					edge_set.push_back(e);

					pch = strtok(NULL, " ,=()\n");
				}
            }
        }
    }

	//add dummy source and sink vertex
	vertex_num = vertex_set.size() + 2;
	for (unsigned int i = 0; i < input_set.size(); i++)
	{
		struct edge e;
		e.in = vertex_num - 2;
		e.out = i;
		edge_set.push_back(e);
	}

	for (unsigned int i = 0; i < output_set.size(); i++)
	{
		struct edge e;
		e.in = i + input_set.size();
		e.out = vertex_num - 1;
		edge_set.push_back(e);
	}

	edge_num = edge_set.size();
	
	gen_fanouts();
	tp_sort();

	//check edge tp
	//remove non tp_order edge
	vector<edge> tmp_edge;
    for (unsigned int i = 0; i < edge_num; i++)
    {
        if (true == check_edge_tp(edge_set[i]))
		{
			tmp_edge.push_back(edge_set[i]);
		}
    }

	edge_set.assign(tmp_edge.begin(), tmp_edge.end());
	edge_num = tmp_edge.size();

    for (unsigned int i = 0; i < edge_num; i++)
    {
        assert(true == check_edge_tp(edge_set[i]));
    }

    // re-index the vertex by tp order and update all edges
    edge_tp_label(); 
   
    //gen_fanins();
    gen_fanouts();

	//add non-ff_edge without fanout to sink
	for (unsigned int i = 0; i < vertex_num -1; i++)
	{
		if (vertex_fanout[i].empty())
		{
			struct edge e;
			e.in = i;
			e.out = vertex_num - 1;
			vertex_fanout[i].push_back(e);
			edge_set.push_back(e);
		}
	}
	edge_num = edge_set.size();
	gen_fanins();

    //verify if vertex is indexed by tp_order
    tp_sort(); 

	fprintf(fp_dag,"%d %d %d \n", vertex_num, 0, edge_num);

    for (unsigned int i = 0; i < vertex_fanin.size(); i++)
    {
        vector<edge>::iterator edge_it;
        for (edge_it = vertex_fanin[i].begin(); 
            edge_it != vertex_fanin[i].end(); ++edge_it)
        {    
			struct edge e;
            e = (*edge_it);
            fprintf(fp_dag,"%d %d\n", e.in, e.out);
        }
    }

    fclose(fp_itc);
    fclose(fp_dag);
}

void ff_graph::ffc_to_dag(char* ffc_file, char* dag_file)
{
    FILE *fp_ffc = fopen (ffc_file, "r");
    FILE *fp_dag = fopen (dag_file, "w");

    if (fp_ffc == NULL || fp_dag == NULL) 
    {
        perror ("Error opening ffc or dag file");
    }

    //jump to file beginning
    rewind (fp_ffc); 
    rewind (fp_dag); 

    //initial a temp edge
    edge e; 
    e.in = 0;
    e.out = 0;

    int a,b;
    fscanf(fp_ffc, " %d %d %d %d %d\n", 
        &gate_num, &a, &edge_num, &b, &ff_num);

    edge_num = 0; //reset edge_num to recount
    edge_set.clear(); 

    // the first ff is host, the combination of src and dist

    //go over the gate type
    char str[100];
    for (unsigned int i = 0; i < gate_num; i++)
    {
        fgets(str, 100, fp_ffc);
    }

    while (!feof (fp_ffc)) 
    {
        fscanf(fp_ffc," %d %d\n", &e.in, &e.out);

        if (e.in > gate_num) //v = gate_num actually the host vertex
        {             
            //continue; // remove reduntant edges in case of cycle
            e.in = gate_num;
        }

        if (e.out == gate_num) //reach host-> reach dist
        {
            e.out = gate_num + ff_num;
        }

        edge_set.push_back(e);
        edge_num++;
    }

    ff_num = ff_num + 1; //split host
    vertex_num = ff_num + gate_num;

    for (unsigned int i = gate_num + 1; i < vertex_num - 1; i++)
    {
        //v = gate_num actually the host vertex, connect ouput 
        e.in = i;
        e.out = vertex_num - 1;
        edge_set.push_back(e);
        edge_num++;
    }

    //generate adjacent lists: fanouts for tp sort
    gen_fanouts();

    //topological sort
#ifndef ITC99
    tp_sort();
#endif

    //check edge tp
    /*for (unsigned int i = 0; i < edge_num; i++)
    {
        assert(true == check_edge_tp(edge_set[i]));
    }*/

    // re-index the vertex by tp order and update all edges
    edge_tp_label(); 
   
    gen_fanins();
    gen_fanouts();

    //verify if vertex is indexed by tp_order
    tp_sort(); 

    //write edge(fanin or fanout) to dag file
    //assert(edge_num == vertex_fanin.size());

    fprintf(fp_dag,"%d %d %d \n", vertex_num, ff_num, edge_num);

    for (unsigned int i = 0; i < vertex_fanin.size(); i++)
    {
        vector<edge>::iterator edge_it;
        for (edge_it = vertex_fanin[i].begin(); 
            edge_it != vertex_fanin[i].end(); ++edge_it)
        {    
            e = (*edge_it);
            fprintf(fp_dag,"%d %d\n", e.in, e.out);
        }
    }

    fclose(fp_ffc);
    fclose(fp_dag);
}

void ff_graph::load_dag(char* dag_file)
{
    FILE *fp = fopen(dag_file, "r");

    if (fp == NULL) 
    {
        perror("Error opening dag file");
    }
    else
    {
        rewind(fp); //jump to file beginning

        //initial a temp edge struct
        edge_set.clear();

        edge e; 
        e.in = 0;
        e.out = 0;
        e.delay = 0.0;

        fscanf(fp, " %d %d %d\n", &vertex_num, &ff_num, &edge_num);
        gate_num = vertex_num - ff_num;

        while (!feof(fp)) 
        {
            fscanf(fp," %d %d\n", &e.in, &e.out);
            edge_set.push_back(e);
        }
    }

    fclose(fp);
}

/*void ff_graph::delay_format(char* delay_file, char* delay_format_file)
{
    FILE *fp = fopen(delay_file,"r");
    FILE *fp_format = fopen(delay_format_file,"w");

    rewind(fp);
    rewind(fp_format);

    unsigned int delay_num;
    unsigned int i = 0; //row index
    float pca; //single pca component

    fscanf(fp," %d %d \n", &gate_num, &delay_column);
    fprintf(fp_format," %d %d \n", gate_num, VARNUM);

    //for BENCH
    //assert(gate_num == delay_num - 1); //check the delay set integrity 
    gate_num -= 1; //last line is zero, which is ff delay
    delay_column += 1; //for BENCH

    //due to relabeling, first vertex is 0 delay, rebuild delay 
    for(unsigned int i = 1; i < gate_num + 1; i++)
    {
        for(unsigned int j = 0; j < delay_column; j++)
        {
            fscanf(fp," %f", &pca);
            if (j < VARNUM - 1)
            {
                fprintf(fp_format," %.6f", pca);
            }
            else if (j == VARNUM - 1)
            {
                fprintf(fp_format," %.6f \n", pca);
            }
        }
        fscanf(fp," %f \n", &pca);
    }

    fclose (fp);
    fclose (fp_format);
}*/

void ff_graph::load_vertex_delay(char* delay_file)
{
    FILE *fp = fopen(delay_file,"r");

    if (fp == NULL) perror ("Error opening vertex delay file");

    rewind(fp);

    unsigned int delay_num;
    float pca; //single pca component

    fscanf(fp," %d %d \n", &vertex_num, &delay_column);

    vertex_delay.assign(get_vertex_num(), vector<float>(delay_column, 0));
    tp_order.clear();

    for(unsigned int i = 0; i < vertex_num; i++)
    {
        for(unsigned int j = 0; j < delay_column; j++)
        {
            fscanf(fp," %f", &pca);
            vertex_delay[i][j] = pca;
        }
        fscanf(fp," \n");
    }

    fclose (fp);
}

void ff_graph::gen_graph(char* dag_file, char* delay_file)
{
    //load graph and random delay
    load_dag(dag_file);
    load_vertex_delay(delay_file);

    gen_fanouts();
    gen_fanins();

    //verify the index by tp_order
    tp_sort(); 
}
